782B - The Meeting Place Cannot Be Changed - CodeForces Solution

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <queue>

#define EPSILON 1e-7

using namespace std;

bool canMeet(vector<int> a, vector<int> v, int N, double t) {
    vector<pair<double, int>> events;
    for (int i = 0; i < N; i++) {
        events.push_back({a[i] - v[i] * t, 1});
        events.push_back({a[i] + v[i] * t, -1});
    }

    sort(events.begin(), events.end(), [](const pair<double, int>& a, const pair<double, int> &b) {
        if (abs(a.first - b.first) < EPSILON) {
            return a.second > b.second;
        } else {
            return a.first < b.first;
        }
    });

    int overlap_max = 0, overlap = 0;
    for (auto it = events.begin(); it != events.end(); it++) {
        overlap += it->second;
        overlap_max = max(overlap_max, overlap);
    }

    return overlap_max == N;
}

// https://codeforces.com/contest/782/problem/B
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    // freopen("meeting-places.in", "r", stdin);
    // freopen("meeting-places.out", "w", stdout);

    int N;
    cin >> N;
    vector<int> a(N), v(N);
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }

    for (int i = 0; i < N; i++) {
        cin >> v[i];
    }

    double low = 0;
    double high = 1e12;
    while (abs(high - low) > EPSILON) {
        double mid = low + (high - low) / 2;
        if (canMeet(a, v, N, mid)) {
            high = mid;
        } else {
            low = mid + EPSILON;
        }
    }

    size_t len = 100;
    char chs[len];
    snprintf(chs, len, "%.6f", low);
    cout << chs << endl;
 }